package com.blue.basic.data.test.pratice;

import java.util.Arrays;
import java.util.List;
import static java.util.stream.Collectors.*;

/**
 * @author liulei, lei.liu@htouhui.com
 * @version 1.0
 */
public class HeapSort {

    public static void main(String[] args) {
        //1.堆排序
        heapSort();
        //2.冒泡排序
//        popSort();
    }
    private static void popSort(){
        int[] data = {16, 7, 3, 20, 17, 8};
        for(int m = 0; m < data.length; m++){
            for(int n = 0; n < data.length -1 - m; n++){
                if(data[n] > data[n+1]){
                    int tmp = data[n];
                    data[n] = data[n+1];
                    data[n+1] = tmp;
                }
            }
        }
        for(Integer integer : data){
            System.out.println(integer);
        }
    }
    private static void heapSort(){
        int[] data = {16, 7, 3, 20, 17, 8};
        //1.根据堆的性质，找到最后的叶子节点
        int lnlIndex = parent(data.length - 1);
        //2.建堆：从后往前遍历非叶子节点，逐个siftDown【此时的堆为最大堆】
        for(int i = lnlIndex; i >= 0 ;i--){
            siftDown(data, i);
        }
        //3.逐步提取堆中最大的元素【1.交换最大堆的根节点和最后一个节点的值 2.从最后一个叶子节点开始siftUp】
        int length = data.length;
        for(int i = length - 1;i>=0;i--){
            System.out.println(data[0]);
            //交換队首-队尾的元素，移除最后一个节点【其实是删除原来的堆根节点】
            data[0] = data[data.length-1];
            List<Integer> list = Arrays.stream(data).boxed().collect(toList());
            //取出堆中最大元素,即第一个元素,删除末尾的元素
            int[] ints = new int[list.size()];
            for(int m=0;m<length-1;m++){
                ints[m]=list.get(m);
            }
            //从0进行下沉
            siftDown(ints, 0);
            data = ints;
        }
    }

    private static int parent(int index) {
        return (index - 1) / 2;
    }
    private static int leftChild(int index) {
        return index * 2 + 1;
    }
    private static int rightChild(int index) {
        return index * 2 + 2;
    }
    /**
     * 建堆操作分解：单个非叶子节点上，进行下沉
     */
    private static void siftDown(int[] data, int index) {
        while(leftChild(index) < data.length){
            int leftIndex = leftChild(index);
            //1.判断是否有右孩子且右孩子的值比左孩子大
            if(rightChild(index) < data.length && data[leftIndex+1] > data[leftIndex]){
                // 始终保持leftIndex的值是左右孩子较大值的index
                leftIndex += 1;
            }
            //2.设置下沉终点：当前节点>左右孩子节点任意值
            if(data[index] > data[leftIndex]){
                break;
            }
            //3.交换值：如果没有到达下沉的终点，交换父节点与左右孩子较大的值
            int tmp = data[index];
            data[index] = data[leftIndex];
            data[leftIndex] = tmp;

            index = leftIndex;
        }
    }


}
